package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no79;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "SCEDA";
        System.out.println(solution.exist(board, word));
    }

    boolean find = false;
    boolean[][] visit = null;

    public boolean exist(char[][] board, String word) {
        find = false;
        visit = new boolean[board.length][board[0].length];
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[x].length; y++) {
                tryFind(board, x, y, word, 0);
                if (find) {
                    return true;
                }
            }
        }
        return false;
    }

    private void tryFind(char[][] board, int x, int y, String word, int index) {
        if (find || index >= word.length()) {
            find = true;
            return;
        }
        if (x >= 0 && x < board.length && y >= 0 && y < board[x].length) {
            if (!visit[x][y] && board[x][y] == word.charAt(index)) {
                visit[x][y] = true;
                tryFind(board, x - 1, y, word, index + 1);
                tryFind(board, x + 1, y, word, index + 1);
                tryFind(board, x, y - 1, word, index + 1);
                tryFind(board, x, y + 1, word, index + 1);
                visit[x][y] = false;
            }
        }
    }
}

